/*
	改进版，只使用了一维数组，减少了空间复杂度 
*/
#include<iostream>
using namespace std;


int dp[205];
int w[35],c[35];
int main(void){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){  //避免数组被覆盖，所以从尾至头比较、修改。
			if(j>=w[i])
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
		}
		for(int k=0;k<=m;k++){	//输出数组 
		cout<<dp[k]<<" ";
		}
		cout<<endl;
	} 
	return 0;
}
